//这里有一个非负整数数组 arr，你最开始位于该数组的起始下标 start 处。当你位于下标 i 处时，你可以跳到 i + arr[i] 或者 i - 
//arr[i]。 
//
// 请你判断自己是否能够跳到对应元素值为 0 的 任一 下标处。 
//
// 注意，不管是什么情况下，你都无法跳到数组之外。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [4,2,3,0,3,1,2], start = 5
//输出：true
//解释：
//到达值为 0 的下标 3 有以下可能方案： 
//下标 5 -> 下标 4 -> 下标 1 -> 下标 3 
//下标 5 -> 下标 6 -> 下标 4 -> 下标 1 -> 下标 3 
// 
//
// 示例 2： 
//
// 输入：arr = [4,2,3,0,3,1,2], start = 0
//输出：true 
//解释：
//到达值为 0 的下标 3 有以下可能方案： 
//下标 0 -> 下标 4 -> 下标 1 -> 下标 3
// 
//
// 示例 3： 
//
// 输入：arr = [3,0,2,1,2], start = 2
//输出：false
//解释：无法到达值为 0 的下标 1 处。 
// 
//
// 
//
// 提示： 
//
// 
// 1 <= arr.length <= 5 * 10^4 
// 0 <= arr[i] < arr.length 
// 0 <= start < arr.length 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 数组 
//
// 👍 129, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class JumpGameIii {
    public static void main(String[] args) {
        Solution solution = new JumpGameIii().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // BFS,DFS都可以
        // https://leetcode.cn/problems/jump-game-iii/solution/tiao-yue-you-xi-iii-by-leetcode-solution/
        public boolean canReach(int[] arr, int start) {
            int n = arr.length;
            LinkedList<Integer>[] graph = new LinkedList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new LinkedList<>();
            }

            // 建图
            for (int i = 0; i < n; i++) {
                int to1 = i - arr[i], to2 = i + arr[i];
                if (to1 >= 0) graph[i].add(to1);
                if (to2 < n) graph[i].add(to2);
            }

            Queue<Integer> queue = new LinkedList<>();
            queue.offer(start);
            boolean[] visited = new boolean[n];
            visited[start] = true;
            while (!queue.isEmpty()) {
                int cur = queue.poll();
                // 遍历到任意一个0
                if (arr[cur] == 0) return true;
                for (int next : graph[cur]) {
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
